/**
 * 面试题13：机器人的运动范围
 */
public class Offer_13 {
    /**
     * 回溯（书中写法）
     */
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        boolean[][] visited = new boolean[m][n];
        return movingCountCore(k, m, n, 0, 0, visited);
    }

    public int movingCountCore(int k, int rows, int cols, int i, int j, boolean[][] visited) {
        int count = 0;
        if (canEnter(k, rows, cols, i, j, visited)) {
            visited[i][j] = true;
            count += 1 + movingCountCore(k, rows, cols, i - 1, j, visited)
                    + movingCountCore(k, rows, cols, i + 1, j, visited)
                    + movingCountCore(k, rows, cols, i, j - 1, visited)
                    + movingCountCore(k, rows, cols, i, j + 1, visited);
        }
        return count;
    }

    /**
     * 判断坐标为 <code>(i,j)</code> 的方格能否进入
     * 
     * @param k       行坐标和列坐标的数位之和的限制
     * @param rows    矩阵的行数
     * @param cols    矩阵的列数
     * @param i       要进入方格的横坐标
     * @param j       要进入方格的纵坐标
     * @param visited 记录访问的矩阵（true为已访问过，false为未访问过）
     * @return 可以进入返回 true，否则返回 false
     */
    public boolean canEnter(int k, int rows, int cols, int i, int j, boolean[][] visited) {
        if (i >= 0 && i < rows && j >= 0 && j < cols && getDigitSum(i) + getDigitSum(j) <= k && !visited[i][j]) {
            return true;
        }
        return false;
    }

    /**
     * 计算一个数字的数位之和
     */
    public int getDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}
